\documentclass[UTF8]{ctexart}
\usepackage{listings} 
\usepackage{xcolor}
\usepackage{fancyhdr}%设置页脚页眉需要的包
\pagestyle{fancy}
\usepackage{graphicx}
\usepackage{cite}
\usepackage{booktabs}
\usepackage{tikz}
\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{float}
\usepackage{amsthm}
\usepackage{xeCJK}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{gnuplottex}
\usepackage{geometry}
\usepackage{enumitem}
\usepackage{verbatimbox}
\usepackage{amsfonts,amssymb} 
\usepackage[ruled,linesnumbered]{algorithm2e}
\usepackage[colorlinks,linkcolor=blue,citecolor=blue]{hyperref}
\usepackage{cite}
\CTEXsetup[format={\Large\bfseries}]{section}
\newtheorem{example}{例}             % 整体编号
\newtheorem{theorem}{定理}[section]  % 按 section 编号
\newtheorem{definition}{定义}
\newtheorem{axiom}{公理}
\newtheorem{property}{性质}
\newtheorem{proposition}{命题}
\newtheorem{lemma}{引理}
\newtheorem{corollary}{推论}
\newtheorem{remark}{注解}
\newtheorem{condition}{条件}
\newtheorem{conclusion}{结论}
\newtheorem{assumption}{假设}
\newcommand{\enabstractname}{Abstract}
\newenvironment{enabstract}{%
    \par\small
    \noindent\mbox{}\hfill{\bfseries \enabstractname}\hfill\mbox{}\par
    \vskip 2.5ex}{\par\vskip 2.5ex}
\usetikzlibrary{positioning, shapes.geometric}
\lstset{
  language=C++,
  frame=shadowbox,
  rulesepcolor=\color{red!20!green!20!blue!20},
  keywordstyle=\color{blue!90}\bfseries,
  commentstyle=\color{red!10!green!70}\textit,
  showstringspaces=false,
  numbers=left,
  numberstyle=\tiny,
  stringstyle=\ttfamily,
  breaklines=true,
  extendedchars=false,
  texcl=true}

\title{Theoretical Assignment III}

\author{韩骐骏 \\ (数学科学学院)信息与计算科学3200103585}

\begin{document}

\maketitle

\section{Problem 3.6.1 I}
\subsection{Question 1}
Consider $p(x)=a_0+a_1x+a_2x^2+a_3x^3$, thus $$p(0)=0,p(1)=(2-x^3)|_{x=1}=1,p'(1)=[(2-x)^3]'|_{x=1}=-3,p''(1)=[(2-x)^3]''|_{x=1}=6,$$ $$a_0=0,a_1+a_2+a_3=1,a_1+-a_2+3a_3=-3,2a_2+6a_3=6$$ That is $$a_0=0,a_1=12,a_2=-18,a_3=7$$ Thus $$p(x)=12x-18x^2+7x^3,s''(0)=p''(0)=-36\neq 0$$Thus $s(x)$ is not a natural cubic spline.\\

\section{Problem 3.6.1 II}
\subsection{Question a}
Consider These $n$ points $x_i$ and $f_i=f(x_i)$ as a basis, it's dimension is $n$. Also from $Theorem 3.14$. we can know that the dimension of $s$ is $2+n-1=n+1>n$, thus we can't find a one-to-one correspondence, an additional condition is needed to determine s uniquely.\\
\subsection{Question b}
\begin{tabular}{c|c|c|c}
    $x_i$ & $f_i$ \\
    $x_i$ & $f_i$   & $m_i$ \\
    $x_{i+1}$ & $f_{i+1}$   & $\frac{f_{i+1}-f_i}{x_{i+1}-x_i}=K_i$   & $\frac{K_i-m_i}{x_{i+1}-x_i}$ \\
\end{tabular}
From the diff table we can compute that $$p_i=s|_{[x_i,x_{i+1}]}=f_i+m_i(x-x_i)+\frac{K_i-m_i}{x_{i+1}-x_i}(x-x_i)^2$$
\subsection{Question c}
Actually we can find that if $p_{i-1}$ is defined by $m_{i-1}$, then we can compute $m_i$ and define $p_i$ uniquely. To ensure the smoothness of $s$, $p_{i-1}'(x_i)=p_i'(x_i)$, that is $$m_{i-1}+2\frac{K_{i-1}-m_{i-1}}{x_i-x_{i-1}}(x_i-x_{i-1})=m_i$$ $$m_{i-1}+m_i=2K_{i-1}$$, $K_{i-1}$ is totally known from $f_i$,$i=1,2,...,n$, and $m_1=f'(a)$ is given, thus we can compute $m_{i}$,$i=2,...,n-1$ one by one.\\

\section{Problem 3.6.1 III}
\subsection{Solution}
Consider $s_2(x)=a_0+a_1x+a_2x^2+a_3x^3$, obviously we've already have $s''(-1)=0$, thus we'll only ensure that $$s_2(0)=s_1(0)=1+c,s_2'(0)=s_1'(0)=3c,s_2''(0)=s_1''(0)=6c,s_2''(1)=0$$That is $$a_0=1+c,a_1=3c,a_2=3c,a_3=\frac{0-2a_2}{6}=-c$$Thus $$s_2(x)=(1+c)+3cx+3cx^2-cx^3$$If one wants $s(1)=s_2(1)=1+6c=-1$, thus $c=-\frac{1}{3}$.\\

\section{Problem 3.6.1 IV}
\subsection{Question a}
Consider $s|_{[-1,0]}=s_1(x)=a_0+a_1x+a_2x^2+a_3x^3$, $s|_{[0,1]}=s_2(x)=b_0+b_1x+b_2x^2+b_3x^3$, thus we have $$s_1''(-1)=0,s_1(-1)=f(-1)=0,s_(0)=f(0)=1$$ $$s_2''(1)=0,s_2(0)=f(0)=1,s_2(1)=f(1)=0$$ $$s_1'(0)=s_2'(0),s_1''(0)=s_2''(0)$$That is $$2a_2-6a_3=0,a_0-a_1+a_2-a_3=0,a_0=1$$ $$2b_2+6b_3=0,b_0=1,b_0+b_1+b_2+b_3=0$$ $$a_1=b_1,a_2=b_2$$Thus we can compute that $$a_0=b_0=1,a_1=b_1=0,a_2=b_2=-\frac{3}{2},a_3=-b_3=-\frac{1}{2}$$Thus we can determine a natural cubic spline.\\
\subsection{Question b}
We can easily find that $g(x)=1-x^2$. By Question a we can compute that $$\int_{-1}^1 [s''(x)]^2 \ dx=2\int_{0}^1 (-3+3x)^2 \ dx=6$$ Also $$\int_{-1}^1 [g''(x)]^2 \ dx=\int_{-1}^1 (-2)^2 \ dx=8>6$$ $$\int_{-1}^1 [f''(x)]^2 \ dx=\int_{-1}^1 [\frac{\pi^2}{4}\cos(\frac{\pi x}{2})]^2 \ dx=\frac{\pi^4}{16}\approx 6.088>6$$Thus the minimal total bending energy theorem is verified.\\

\section{Problem 3.6.1 V}
\subsection{Question a}
We've already have
\begin{equation}
B_i^1(x)=\left\{
	\begin{aligned}
	\frac{x-t_{i-1}}{t_i-t_{i-1}} \quad ,x\in(t_{i-1},t_i]\\
	\frac{t_{i+1}-x}{t_{i+1}-t_i} \quad ,x\in(t_i,t_{i+1}\\
	0 \quad ,otherwise\\
	\end{aligned}
	\right
	.
\end{equation}
We also have $$B_i^{n+1}(x)=\frac{x-t_{i-1}}{t_{i+n}-t_{i-1}}B_i^n(x)+\frac{t_{i+n+1}-x}{t_{i+n+1}-t_i}B_{i+1}^n(x)$$Thus we can compute that 
\begin{equation}
B_i^2(x)=\left\{
	\begin{aligned}
	\frac{(x-t_{i-1})^2}{(t_i-t_{i-1})(t_{i+1}-t_{i-1})} \quad ,x\in(t_{i-1},t_i]\\
	\frac{(t_{i+1}-x)(x-t_{i-1})}{(t_{i+1}-t_i)(t_{i+1}-t_{i-1})}+\frac{(x-t_i)(t_{i+2}-x)}{(t_{i+1}-t_i)(t_{i+2}-t_i)} \quad ,x\in(t_i,t_{i+1}]\\
	\frac{(t_{i+2}-x)^2}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})} \quad ,x\in(t_{i+1},t_{i+2}]\\
	0 \quad ,otherwise\\
	\end{aligned}
	\right
	.
\end{equation}
\subsection{Question b}
\begin{equation}
\frac{dB_i^2(x)}{dx}=\left\{
	\begin{aligned}
	\frac{2(x-t_{i-1})}{(t_i-t_{i-1})(t_{i+1}-t_{i-1})} \quad ,x\in(t_{i-1},t_i]\\
	\frac{t_{i+1}+t_{i-1}-2x}{(t_{i+1}-t_i)(t_{i+1}-t_{i-1})}+\frac{t_i+t_{i+2}-2x}{(t_{i+1}-t_i)(t_{i+2}-t_i)} \quad ,x\in(t_i,t_{i+1}]\\
	\frac{2(x-t_{i+2})}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})} \quad ,x\in(t_{i+1},t_{i+2}]\\
	0 \quad ,otherwise\\
	\end{aligned}
	\right
	.
\end{equation}
We substitute $x$ with $t_i$ and $t_{i+1}$, $$\frac{dB_i^2(x)}{dx}|_{x=t^-_i}=\frac{2(t_i-t_{i-1})}{(t_i-t_{i-1})(t_{i+1}-t_{i-1})}=\frac{2}{t_{i+1}-t_{i-1}}$$ $$\frac{dB_i^2(x)}{dx}|_{x=t^+_i}=\frac{t_{i+1}+t_{i-1}-2t_i}{(t_{i+1}-t_i)(t_{i+1}-t_{i-1})}+\frac{t_i+t_{i+2}-2t_i}{(t_{i+1}-t_i)(t_{i+2}-t_i)}=\frac{2}{t_{i+1}-t_{i-1}}$$ $$\frac{dB_i^2(x)}{dx}|_{x=t^-_{i+1}}=-\frac{1}{t_{i+1}-t_i}+\frac{t_i+t_{i+2}-2t_{i+1}}{(t_{i+1}-t_i)(t_{i+2}-t_i)}=\frac{2}{t_i-t_{i+2}}$$ $$\frac{dB_i^2(x)}{dx}|_{x=t^+_{i+1}}=\frac{2(t_{i+1}-t_{i+2})}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})}=\frac{2}{t_i-t_{i+2}}$$Thus $$\frac{dB_i^2(x)}{dx}|_{x=t^-_i}=\frac{dB_i^2(x)}{dx}|_{x=t_i}=\frac{dB_i^2(x)}{dx}|_{x=t^+_i},\frac{dB_i^2(x)}{dx}|_{x=t^-_{i+1}}=\frac{dB_i^2(x)}{dx}|_{x=t_{i+1}}=\frac{dB_i^2(x)}{dx}|_{x=t^+_{i+1}}$$ $\frac{dB_i^2(x)}{dx}$ is continuous at $t_i$ and $t_{i+1}$.\\
\subsection{Question c}
By Question b we can compute that $$x^*=\frac{t_{i+2}t_{i+1}-t_it_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}}\in (t_{i-1},t_{i+1})$$Only $x^*$ satisfies $\frac{dB_i^2(x)}{dx}|_{x=x^*}=0,x\in(t_{i-1},t_{i+1})$.\\
\subsection{Question d}
\begin{equation}
\frac{dB_i^2(x)}{dx}=\left\{
	\begin{aligned}
	\geq 0 \quad ,x\in(t_{i-1},x^*]\\
	\leq 0 \quad ,x\in(x^*,t_{i+2}]\\
	=0 \quad ,otherwise\\
	\end{aligned}
	\right
	.
\end{equation}
Thus $$\max B_i^2(x)=B_i^2(x^*)=\frac{(t_{i+1}-x^*)(x^*-t_{i-1})}{(t_{i+1}-t_i)(t_{i+1}-t_{i-1})}+\frac{(x^*-t_i)(t_{i+2}-x^*)}{(t_{i+1}-t_i)(t_{i+2}-t_i)}$$ $$\max B_i^2(x)=\frac{(t_{i+1}-\frac{t_{i+2}t_{i+1}-t_it_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}})(\frac{t_{i+2}t_{i+1}-t_it_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}}-t_{i-1})}{(t_{i+1}-t_i)(t_{i+1}-t_{i-1})}+\frac{(\frac{t_{i+2}t_{i+1}-t_it_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}}-t_i)(t_{i+2}-\frac{t_{i+2}t_{i+1}-t_it_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}})}{(t_{i+1}-t_i)(t_{i+2}-t_i)}$$ $$\max B_i^2(x)=\frac{t_{i+2}-t_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}}<1$$ $$\min B_i^2(x)=\min \{0,B_i^2(t_{i-1}),B_i^2(t_{i+2})\}=0$$Thus $B_i^2(x)\in[0,1)$.\\
\subsection{Question e}
For different $i$, the image is only horizontally translated, so it is better to set $i=0$.
\begin{figure}[htp]
    \centering
    \includegraphics[width=13cm]{pic1}
    \caption{V.(e)}
    \label{fig:galaxy}
\end{figure}

\section{Problem 3.6.1 VI}
\subsection{Solution}
$$(t_{i+2}-t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}]=[t_i,t_{i+1},t_{i+2}]-[t_{i-1},t_i,t_{i+1}]=\frac{[t_{i+1},t_{i+2}]-[t_i,t_{i+1}]}{t_{i+2}-t_i}-\frac{[t_i,t_{i+1}]-[t_{i-1},t_i]}{t_{i+1}-t_{i-1}}$$Thus $$(t_{i+2}-t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t-x)_+^2=\frac{\frac{(t_{i+2}-x)_+^2-(t_{i+1}-x)_+^2}{t_{i+2}-t_{i+1}}-\frac{(t_{i+1}-x)_+^2-(t_{i}-x)_+^2}{t_{i+1}-t_{i}}}{t_{i+2}-t_i}-\frac{\frac{(t_{i+1}-x)_+^2-(t_{i}-x)_+^2}{t_{i+1}-t_{i}}-\frac{(t_{i}-x)_+^2-(t_{i-1}-x)_+^2}{t_{i}-t_{i-1}}}{t_{i+1}-t_{i-1}}$$When $x>t_{i+2}$ $$(t_{i-1}-x)_+^2=(t_{i}-x)_+^2=(t_{i+1}-x)_+^2=(t_{i+2}-x)_+^2=0$$Thus $$(t_{i+2}-t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t-x)_+^2=B_i^2,x\in(t_{i+2},+\infty]$$Similarly we sequentially investigates $x\in(t_{i-1},t_i],x\in(t_{i},t_{i+1}],x\in(t_{i+1},t_{i+2}]$, we can find that $(t_{i+2}-t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t-x)_+^2=B_i^2$.\\

\section{Problem 3.6.1 VII}
\subsection{Solution}
$$0=B^{n+1}_i(x)|^{t_{i+n+1}}_{t_{i-1}}=\int_{t_{i-1}}^{t_{i+n+1}} \frac{dB^{n+1}_i(x)}{dx} \ dx$$ By $$\frac{dB^{n+1}_i(x)}{dx}=\frac{(n+1)B^n_i(x)}{t_{i+n}-t_{i-1}}-\frac{(n+1)B^n_{i+1}(x)}{t_{i+n+1}-t_i}$$We know that $$\int_{t_{i-1}}^{t_{i+n+1}} \frac{(n+1)B^n_i(x)}{t_{i+n}-t_{i-1}} \ dx=\int_{t_{i-1}}^{t_{i+n+1}} \frac{(n+1)B^n_{i+1}(x)}{t_{i+n+1}-t_i} \ dx$$ $$\int_{t_{i-1}}^{t_{i+n}} \frac{B^n_i(x)}{t_{i+n}-t_{i-1}} \ dx=\int_{t_{i}}^{t_{i+n+1}} \frac{B^n_{i+1}(x)}{t_{i+n+1}-t_i} \ dx$$From this, we can recursively get $\forall i,j$ $$\int_{t_{i-1}}^{t_{i+n}} \frac{B^n_i(x)}{t_{i+n}-t_{i-1}} \ dx=\int_{t_{j-1}}^{t_{j+n}} \frac{B^n_{j}(x)}{t_{j+n}-t_{j-1}} \ dx$$Thus the scaled integral of a B-spline $B^n_i(x)$ over its support is independent of its index $i$.\\

\section{Problem 3.6.1 VIII}
\subsection{Question a}
\begin{tabular}{c|c|c|c}
    $x_i$ & $x^4_i$ \\
    $x_{i+1}$ & $x^4_{i+1}$   & $x^3_{i+1}+x^3_{i}+x^2_{i+1}x_{i}+x_{i+1}x^2_{i}$ \\
    $x_{i+2}$ & $x^4_{i+2}$   & $x^3_{i+2}+x^3_{i+1}+x^2_{i+2}x_{i+1}+x_{i+2}x^2_{i+1}$   & $x^2_{i}+x^2_{i+1}+x^2_{i+2}+x_{i}x_{i+1}+x_{i+1}x_{i+2}+x_{i}x_{i+2}$ \\
\end{tabular}
Thus we get $\tau_2(x_i,x_{i+1},x_{i+2})=[x_i,x_{i+1},x_{i+2}]x^4$.\\
\subsection{Question b}
For $\forall m$, obviously $\tau_m(x_i)=[x_i]x^m$. Now let's fix $m$ unchanged and use induction for $n$. By $$\tau_{m-n}(x_i,...,x_{i+n})=\tau_{m-n}(x_i,...,x_{i+n+1})-x_{i+n+1}\tau_{m-n-1}(x_i,...,x_{i+n+1})$$ $$\tau_{m-n}(x_{i+1},...,x_{i+n+1})=\tau_{m-n}(x_i,...,x_{i+n+1})-x_{i}\tau_{m-n-1}(x_{i},...,x_{i+n+1})$$We have $$\tau_{m-n}(x_{i+1},...,x_{i+n+1})-\tau_{m-n}(x_i,...,x_{i+n})=(x_{i+n+1}-x_i)\tau_{m-n-1}(x_i,...,x_{i+n+1})$$Thus $$\tau_{m-(n+1)}(x_i,...,x_{i+n+1})=\frac{\tau_{m-n}(x_{i+1},...,x_{i+n+1})-\tau_{m-n}(x_i,...,x_{i+n})}{(x_{i+n+1}-x_i)}$$ $$\tau_{m-(n+1)}(x_i,...,x_{i+n+1})=\frac{[x_{i+1},...,x_{i+n+1}]x^m-[x_i,...,x_{i+n}]x^m}{(x_{i+n+1}-x_i)}$$ $$\tau_{m-(n+1)}(x_i,...,x_{i+n+1})=[x_i,...,x_{i+n+1}]x^m$$So we conclude and prove the theorem.\\

\end{document}
